package com.hjx.leetcode;

import java.io.IOException;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Pattern;

/**
 * 10. 正则表达式匹配
 *
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 *
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 *
 * 说明:
 *
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 *
 * 示例 1:
 *
 * 输入:
 *       s = "aa"
 *       p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 *
 * 示例 2:
 *
 * 输入:
 *       s = "aa"
 *       p = "a*"
 * 输出: true
 * 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 *
 * 示例 3:
 *
 * 输入:
 *       s = "ab"
 *       p = ".*"
 * 输出: true
 * 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 *
 * 示例 4:
 *
 * 输入:
 *       s = "aab"
 *       p = "c*a*b"
 * 输出: true
 * 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 *
 * 示例 5:
 *
 * 输入:
 *       s = "mississippi"
 *       p = "mis*is*p*."
 * 输出: false
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/regular-expression-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class LeetCode_10 {

    private int i;

    /**
     * 递归法
     * 1、无特殊符号的情况,则只考虑s!=null && p != null && s.equals(p)即可
     * 2、考虑有 . 的情况，若用递归方法，以s = abcd p = ab.d 比较则过程如下：
     *     (1) 若s[0] == p[0] || p[0] == '.'  则判断 s[1-3] 是否匹配p[1-3]
     *     (2) 若s[1] == p[1] || p[1] == '.'  则判断 s[2-3] 是否匹配p[2-3]
     *     (3) 若s[2] == p[2] || p[2] == '.'  则判断 s[3] 是否匹配p[3]
     *     (4) 若s[3] == p[3] || p[3] == '.'  则 s[2-3] 匹配 p[2-3]
     *     (5) 若s[2-3] 匹配 p[2-3]  则 s[1-3] 匹配 p[1-3]
     *     (6) 若s[1-3] 匹配 p[1-3]  则 s[0-3] 匹配 p[0-3]
     *     (7) 则 s 匹配 p
     *
     * 3、考虑 * * 代表 0或多次
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        if (s == null) return false;
        if (s.equals(p)){
            return true;
        }
        if (p.length() == 0) {
            return s.length() == 0;
        }
//        System.out.println(i++ +". s:\""+s+"\"  p:\""+p+"\"");
        boolean matchOrNot = s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');

        //p 只有在>=2 时 才会存在第二位为*的情况
        if(p.length() >= 2 && p.charAt(1) == '*'){
            //若*后面的第一位等于当前s的第一位 则 匹配到0次,先匹配 并作短路处理
            //若*前面一位等于当前s的第一位,则继续匹配s的后续字符看是否匹配p
            return isMatch(s, p.substring(2)) ||
                (matchOrNot && isMatch(s.substring(1), p));

        }
        return matchOrNot && isMatch(s.substring(1), p.substring(1));
    }


    /**
     * 初始版本，未能覆盖所有情况，总是会出现新的用例不满足的情况
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch1(String s, String p) {
        List<char[]> rules = new ArrayList<>();
        int begin = 0;
        char[] pChars = p.toCharArray();
        char[] sChars = s.toCharArray();
        for (int i = 0; i < pChars.length; i++) {
            //遇到 * 则分割p
            if (pChars[i] == '*'){
                //先截取，在移动开始下标
                rules.add(p.substring(begin, i + 1).toCharArray());
                if (i != pChars.length - 1 ){
                    begin = i+1;
                }

            } else if (i == pChars.length - 1){
                //最后一位，且不为 *
                rules.add(p.substring(begin, pChars.length).toCharArray());
            }
        }

        rules.forEach(item->{
            System.out.print(new String(item) + "|");
        });
        System.out.println();

        int b = 0;
        int rb = 0;
        for(char[] rule : rules){
            //如果规则最后是个星, 说明要多次匹配
            if (rule[rule.length-1] == '*' && sChars.length > 0){

                //前n-2位必须一模一样 或 规则中含"." n = rule.length
                for (int i = 0; i < rule.length - 2; i++) {
                    //两字符不一样且规则字符不是'.'直接返回
                    if(sChars[b] != rule[i] && rule[i] != '.'){
                        return false;
                    }
                    b++;
                }
                //如果到了最后一位直接返回匹配
                if (b == sChars.length){
                    return true;
                }
                //通过检验，比较字符串下标rule.length - 1开始的字符
                rb = rule.length - 2;
//                    e = chars.length - 1;
                //此时有两种情况
                //1.首位不相同
                     //1)规则串首位不是'.', 匹配到0次，匹配结束
                     //2)规则串首位是'.',匹配到最后，结束
                //2.首位相同，直到遇到一个不相同的字符为止,记录该字符的下标，记为下次循环的其实位置
                if (sChars[b] != rule[rb]){
                    if (rule[rb] == '.'){
                        return true;
                    }
                } else {
                    while(b != sChars.length && sChars[b] == rule[rb]){
                        b++;
                    }
                    if (b == sChars.length){
                        return true;
                    }
                }

            } else {
                //若剩余字符串长度不等于规则长度则不匹配
                if (rule.length != sChars.length - b){
                    return false;
                }
                //逐个比较
                for (int j = 0; j < rule.length; j++){
                    if(sChars[b] != rule[j] && rule[j] != '.'){
                        return false;
                    }
                    b++;
                }
            }
        }
        //一般情况 所有规则，要把所有字符串都过一遍，才能得出是否匹配，除非一些明显能判断出是否匹配的条件，否则都要看b是否遍历到头
        return b == sChars.length;
    }
}
